10699. Подсчет делителей

По заданному положительному целому числу n вычислить количество его простых делителей.

Вход. Каждая входная строка содержит число n (n £ 1000000). Число n = 0 является концом входных данных и не обрабатывается.

Выход. Для каждого числа n вывести количество его простых делителей в формате, приведенном в примере.

Пример входа

289384
930887
692778
636916
747794
238336
885387
760493
516650
641422
0

Пример выхода

289384 : 3
930887 : 2
692778 : 5
636916 : 4
747794 : 3
238336 : 3
885387 : 2
760493 : 2
516650 : 3
641422 : 3

РЕШЕНИЕ

разложение на множители

Анализ алгоритма

Перебираем последовательно делители числа n, начиная с 2. При обнаружении делителя делим n на него до тех пор пока деление возможно без остатка. Делители ищем до тех пор, пока n не станет равным 1.

Пример

Рассмотрим первый тест. Делителями числа n = 289384 будут 2, 61 и 593, так как 289384 = 2³ * 61 * 593. Таким образом, число 289384 имеет 3 делителя.

Реализация алгоритма

Читаем значение n, обнуляем счетчик количества делителей count. Запоминаем исходное значение n в переменной tempn.

while (scanf("%d",&n),n)

{

count = 0; tempn = n;

Для каждого значения i = 2, 3, ... проверяем, является ли оно делителем n. Если является, то увеличиваем count на 1 и делим n на i до тех пор, пока деление проводится без остатка.

for(i = 2; i <= n; i++)

{

if (n % i == 0) count++;

while (n % i == 0) n = n / i;

}

Выводим исходное число n и вычисленное количество делителей.

printf("%d : %d\n",tempn,count);

}